package LintCode;

import java.util.*;

/**
 * @Classname ThreeSum
 * @Description TODO
 * @Date 2021/3/4 8:46
 * @Created by ASUS
 */
public class ThreeSum {

    /**
     * 三数之和
     *
     * @param data 传入数组
     * @return 满足条件的所有解
     */
    public List<List<Integer>> threeSum(int[] data) {
        List<List<Integer>> result = new ArrayList<>();
        if (data == null || data.length < 3) return result;
        Arrays.sort(data);
        System.out.println(Arrays.toString(data));
        if (data[0] > 0 || data[data.length - 1] < 0) return result;
        for (int i = 0; i < data.length - 2; i++) {
            if (i > 0 && data[i] == data[i - 1]) {
                continue;
            }
            int target = -data[i];
            int left = i + 1;
            int right = data.length - 1;
            while (left < right) {
                if (target == data[left] + data[right]) {
                    List<Integer> tmpList = new ArrayList<>();
                    tmpList.add(data[i]);
                    tmpList.add(data[left++]);
                    tmpList.add(data[right--]);
                    result.add(tmpList);
                    while (data[left] == data[left - 1] && left < right) left++;
                    while (data[right] == data[right + 1] && right > left) right--;
                } else if (target > data[left] + data[right]) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new ThreeSum().threeSum(new int[]{1, 0, -1, -1, -1, -1, 0, 1, 1, 1}));
    }
}
